package com.lft.search04.fibonacci_search;

import java.util.Arrays;

/**
 * Function: 		A {@code FibonacciSearch} object With Some FUNCTION.<br/>
 * Reason:   		ADD REASON.<br/>
 * Date:            2021-03-07 13:30<br/>
 * <p>
 * Class Name:      FibonacciSearch<br/>
 * Package Name:    com.lft.search04.fibonacci_search<br/>
 * @author Laifengting / E-mail:laifengting@foxmail.com
 * @version 1.0.0
 * @since JDK 8
 */
public class FibonacciSearch {
	public static void main(String[] args) {
		int[] a = {1, 8, 10, 89, 1000, 1234};
		System.out.println("索引是：" + fibSerach(a, 22));
	}
	
	/**
	 * 因为后面我们 mid = low + F(k-1) - 1，需要使用到斐波那契数列，因此我们需要先获取到一个斐波那契数列
	 * 非递归方法得到一个斐波那契数列
	 * @param maxSize 斐波那契数列的最大长度
	 * @return 返回创建好的斐波那契数列
	 */
	public static int[] fib(int maxSize) {
		int[] f = new int[maxSize];
		f[0] = 1;
		f[1] = 1;
		for (int i = 2; i < maxSize; i++) {
			f[i] = f[i - 1] + f[i - 2];
		}
		return f;
	}
	
	/**
	 * 斐波那契查找算法。
	 * 【非递归】
	 * @param a     原始数组
	 * @param value 要查找的值
	 * @return 查找到值的索引，如果没有返回 -1。
	 */
	public static int fibSerach(int[] a, int value) {
		int low = 0;
		int high = a.length - 1;
		
		// 表示斐波那契分割数值对应的下标。
		int k = 0;
		
		int mid = 0;
		int[] f = fib(20);
		
		// 获取斐波那契分割数值的下标
		while (high > f[k] - 1) {
			k++;
		}
		
		// 因为 f[k] 值 可能大于 a 的长度，因此我们需要使用 Arrays 类，构造一个新的数组，并指向 temp[]
		int[] temp = Arrays.copyOf(a, f[k]);
		
		// 实际上需要使用 a 数组最后的数值填充 temp
		// 举例：
		// temp = {1, 8, 10, 89, 1000, 1234, 0, 0, 0} => temp = {1, 8, 10, 89, 1000, 1234, 1234, 1234, 1234}
		for (int i = high + 1; i < temp.length; i++) {
			temp[i] = a[high];
		}
		
		// 使用 while 循环来处理，找到我们的数 value
		while (low <= high) {
			mid = low + f[k - 1] - 1;
			// 向左查找
			if (value < temp[mid]) {
				high = mid - 1;
				// 为什么是k--
				// 说明：
				// 1. 全部元素 = 前面的元素 + 后面的元素
				// 2. f[k] = f[k-1] + f[k-2]
				// 因为前面有 f[k-1] 个元素，可以再拆分，f[k-1] = f[k-2] + f[k-3]
				// 即 在 f[k-1] 的前面继续查找，k--
				// 即下次循环 mid = f[k-1-1]-1
				k--;
			} else if (value > temp[mid]) {
				low = mid + 1;
				// 为什么是k-=2
				// 说明：
				// 1. 全部元素 = 前面的元素 + 后面的元素
				// 2. f[k] = f[k-1] + f[k-2]
				// 因为后有 f[k-2] 个元素，可以再拆分，f[k-2] = f[k-3] + f[k-4]
				// 即 在 f[k-2] 的后面继续查找，k-=2
				// 即下次循环 mid = f[k-1-2]-1
				k -= 2;
			} else {
				// 需要确定，返回的是哪个下标
				if (mid <= high) {
					return mid;
				} else {
					return high;
				}
			}
		}
		// 没有找到返回 -1
		return -1;
	}
	
}
